import collections


class ArrayDeque:
    """基于数组的双端队列
    Python的标准collections模块中有一个双端队列类的实现方法
    """
    DEFAULT_LENGTH = 10

    def __init__(self):
        self.deque = [None] * self.DEFAULT_LENGTH
        self.front = 0
        self.size = 0

    def add_first(self,data):
        if self.size == len(self.deque):
            self.resize(2 * len(self.deque))
        self.front = (self.front - 1) % len(self.deque)
        self.deque[self.front] = data
        self.size += 1

    def add_last(self,data):
        if self.size == len(self.deque):
            self.resize(2 * len(self.deque))
        last = (self.front + self.size) % len(self.deque)
        self.deque[last] = data
        self.size += 1

    def del_first(self):
        if self.is_empty():
            raise Exception('队列为空')
        data,self.deque[self.front] = self.deque[self.front],None
        self.front = (self.front + 1) % len(self.deque)
        self.size -= 1
        if 0 < self.size < (len(self.deque) // 4):
            self.resize(len(self.deque) // 2)
        return data

    def del_last(self):
        if self.is_empty():
            raise Exception('队列为空')
        last = (self.front + self.size - 1) % len(self.deque)
        data,self.deque[last] = self.deque[last],None
        self.size -= 1
        if 0 < self.size < (len(self.deque) // 4):
            self.resize(len(self.deque) // 2)
        return data

    def first(self):
        if self.is_empty():
            raise Exception('队列为空')
        return self.deque[self.front]

    def last(self):
        if self.is_empty():
            raise Exception('队列为空')
        last = (self.front + self.size - 1) % len(self.deque)
        return self.deque[last]

    def __len__(self):
        return self.size

    def resize(self,length):
        old_deque = self.deque
        old_len = len(self.deque)
        self.deque = [None] * length
        index = self.front
        for i in range(self.size):
            self.deque[i] = old_deque[index]
            index = (index + 1) % old_len
        self.front = 0

    def is_empty(self):
        return self.size == 0

    def __str__(self):
        msg = str(self.deque)
        return msg


if __name__ == '__main__':
    arr1 = ArrayDeque()
    deque = collections.deque()
    arr1.add_last(5)
    print(arr1)
    arr1.add_first(3)
    print(arr1)
    arr1.add_first(7)
    print(arr1)
    arr1.del_last()
    print(arr1)
    for i in range(10):
        arr1.add_first(i)
        print(arr1)
    print(arr1)
    arr1.del_first()
    print(arr1)
    arr1.del_last()
    print(arr1)
    arr1.del_last()
    print(arr1)
    arr1.del_last()
    arr1.del_last()
    arr1.del_last()
    arr1.del_last()
    arr1.del_last()
    arr1.del_last()
    print(arr1)
